import com.sun.java.swing.plaf.windows.WindowsDesktopIconUI;

//模拟实现一个哈希  ： 数组加链表
public class HashBuck {
    static class Node {
        public int val;
        public int key;
        public Node next;

        public Node(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }
    public Node[] array;  //数组中存放的都是Node类型的节点
    public int usedSize;  //记录存放数据的多少

    public static final double LOAD_FACTOR = 0.75;  //负载因子

    public HashBuck() {
        array = new Node[10];  //仅用于自己实现，源码不是如此
    }

    //模拟实现哈希表的放入数据 ， 设置key对应的val
    public void put(int key,int val) {
        int index = key % array.length;  //相当于一个哈希函数
        Node node = new Node(key,val);
        //array[index] = node;
        Node cur = array[index];
        //判断放的位置是不是空的，若是空的，直接放，若不空，这个空格内加入链表结构
        if(array[index] == null) {
            array[index] = node;
            usedSize++;
        } else {
            while(cur != null) {
                if(cur.key == key) {   //这里说明原先保存的有这个key，更新它的次数即可
                                       //因为哈希表中不添加重复的值，只会更新它的val值
                    cur.val = val;
                    return;
                }
                cur = cur.next;
            }
            //走到这说明保存的没有这个key，需要进行插入，在此采用头插的方式
            cur = array[index];
            node.next = cur;
            cur = node;
            usedSize++;

            /**
             * 这里注意cur要再指回来给array[index]，不然不会发生变化的，和下面 ============= 注释的原因是一个
             */
            array[index] = cur;
            /**
             *          注意扩容函数的位置放错了，应该放在 if的外面，每次添加完新的都要检查一下容量
             *   //判断是否需要扩容
             *             if(calculateLoadFactor() >= LOAD_FACTOR) {
             *                 //扩容
             *                 resize();
             *             }
             */

        }
        //判断是否需要扩容
        if(calculateLoadFactor() >= LOAD_FACTOR) {
            //扩容
            resize();
        }
    }

    private void resize() {
        Node[] arrayNew = new Node[2 * array.length];
        //再把原先的值放到新的数组里面
        for (int i = 0; i < array.length; i++) {
            //注意此时放的下标由于数组的扩容而会发生变化
            int index = i % arrayNew.length;
            /**
             *     ============================
             * 注意这种写法不对，
             *   for (int i = 0; i < array.length; i++) {
             *             //注意此时放的下标由于数组的扩容而会发生变化
             *             int index = i % arrayNew.length;
             *              arrayNew[index] = array[i];
             *          }
             * 因为下标由于数组的扩容而会发生变化，所以会有可能由后面的i计算出的新下标跟前面的重复，而导致覆盖问题发生错误
             * 正确的应该是找到节点继续一个一个地头插
             *arrayNew[index] = array[i];
              **/
            Node cur = array[i];
            //Node curNew = arrayNew[index];
            while(cur != null) {
                Node curNext = cur.next;
                //把cur的节点一个一个地以头插的方式插入到新节点中去
                cur.next = arrayNew[index];
                arrayNew[index] = cur;
                cur = curNext;
                //arrayNew[index] = curNew;
            }
            //arrayNew[index] = curNew;

            /**
             *    上面的代码也可以写成这种，这种格式更加直接，
             *    上面那种是赋值的，需要再给到原来的arrayNew[index] 节点处， 不然不会发生改变
             *          while(cur != null) {
             *                 Node curNext = cur.next;
             *                 //把cur的节点一个一个地以头插的方式插入到新节点中去
             *                 cur.next = arrayNew[index];
             *                 arrayNew[index] = cur;
             *                 cur = curNext;
             *          }
             */
        }
        array = arrayNew;
    }

    //计算负载因子
    private double calculateLoadFactor() {
        return usedSize*1.0 / array.length;
    }

    //返回key对应的val值
    public int get(int key) {
//        for (int i = 0; i < array.length; i++) {
//        }
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.val;
            } else {   //这里其实用不到else，因为这两个不可能同时出现，因为上面有return，走上一步就不可能走下面了，直接返回了
                cur = cur.next;
            }
        }
        return -1;
    }
}
